{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game VIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #graph #array #dynamic-programming #shortest-path #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #图 #数组 #动态规划 #最短路 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 VIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 n 的下标从 <strong>0</strong>&nbsp;开始的整数数组 <code>nums</code>。初始位置为下标 <code>0</code>。当 <code>i &lt; j</code> 时，你可以从下标 <code>i</code> 跳转到下标 <code>j</code>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于在&nbsp;<code>i &lt; k &lt; j</code>&nbsp;范围内的所有下标 <code>k</code> 有&nbsp;<code>nums[i] &lt;= nums[j]</code> 和&nbsp;<code>nums[k] &lt; nums[i]</code> , 或者</li>\n",
    "\t<li>对于在&nbsp;<code>i &lt; k &lt; j</code>&nbsp;范围内的所有下标 <code>k</code>&nbsp;有&nbsp;<code>nums[i] &gt; nums[j]</code> 和&nbsp;<code>nums[k] &gt;= nums[i]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你还得到了一个长度为 <code>n</code> 的整数数组 <code>costs</code>，其中 <code>costs[i]</code> 表示跳转<strong>到</strong>下标 <code>i</code> 的代价。</p>\n",
    "\n",
    "<p>返回<em>跳转到</em>下标 <em><code>n - 1</code> 的最小代价。</em></p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [3,2,4,4,1], costs = [3,7,6,4,2]\n",
    "<strong>输出:</strong> 8\n",
    "<strong>解释:</strong> 从下标 0 开始。\n",
    "- 以 costs[2]= 6 的代价跳转到下标 2。\n",
    "- 以 costs[4]= 2 的代价跳转到下标 4。\n",
    "总代价是 8。可以证明，8 是所需的最小代价。\n",
    "另外两个可能的路径是:下标 0 -&gt; 1 -&gt; 4 和下标 0 -&gt; 2 -&gt; 3 -&gt; 4。\n",
    "它们的总代价分别为9和12。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1,2], costs = [1,1,1]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 从下标 0 开始。\n",
    "- 以 costs[1] = 1 的代价跳转到下标 1。\n",
    "- 以 costs[2] = 1 的代价跳转到下标 2。\n",
    "总代价是 2。注意您不能直接从下标 0 跳转到下标 2，因为 nums[0] &lt;= nums[1]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>解释:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length == costs.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i], costs[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-viii](https://leetcode.cn/problems/jump-game-viii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-viii](https://leetcode.cn/problems/jump-game-viii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,4,1]\\n[3,7,6,4,2]', '[0,1,2]\\n[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        dp = [0] * length\n",
    "        stack1 = [0]\n",
    "        # stack1 is the first\n",
    "        stack2 = [0]\n",
    "        # stack2 is the second\n",
    "        for i in range(1, length):\n",
    "            value = float('inf')\n",
    "            while len(stack1) > 0 and nums[i] >= nums[stack1[-1]]:\n",
    "                value = min(value, dp[stack1[-1]] + costs[i])\n",
    "                stack1.pop()\n",
    "            stack1.append(i)\n",
    "            while len(stack2) > 0 and nums[i] < nums[stack2[-1]]:\n",
    "                value = min(value, dp[stack2[-1]] + costs[i])\n",
    "                stack2.pop()\n",
    "            stack2.append(i)\n",
    "            \n",
    "            dp[i] = value\n",
    "        return dp[length - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        ls,hs=[0],[0]\n",
    "        for i,k in enumerate(nums[1:],1):\n",
    "            dp[i]=dp[i-1]\n",
    "            while ls and nums[ls[-1]]<=k:\n",
    "                dp[i]=min(dp[i],dp[ls.pop()])\n",
    "            while hs and nums[hs[-1]]>k:\n",
    "                dp[i]=min(dp[i],dp[hs.pop()])\n",
    "            dp[i]+=costs[i]\n",
    "            ls.append(i)\n",
    "            hs.append(i)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        ls,hs=[0],[0]\n",
    "        for i,k in enumerate(nums[1:],1):\n",
    "            dp[i]=dp[i-1]+costs[i]\n",
    "            while ls and nums[ls[-1]]<=k:\n",
    "                dp[i]=min(dp[i],dp[ls.pop()]+costs[i])\n",
    "            while hs and nums[hs[-1]]>k:\n",
    "                dp[i]=min(dp[i],dp[hs.pop()]+costs[i])\n",
    "            ls.append(i)\n",
    "            hs.append(i)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minv = [-1 for _ in range(n)]\n",
    "        maxv = [-1 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: minv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] < nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: maxv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "# ## dij\n",
    "        # for i in range(n):\n",
    "        #     if minv[i] != -1:\n",
    "        #         edges[i].append(minv[i])\n",
    "        #     if maxv[i] != -1:\n",
    "        #         edges[i].append(maxv[i])\n",
    "\n",
    "#         dis = [float('inf') for _ in range(n)]\n",
    "#         dis[0] = 0\n",
    "#         heap = []\n",
    "#         heapq.heappush(heap,[0,0])\n",
    "#         while heap:\n",
    "#             d,cur = heapq.heappop(heap)\n",
    "#             # if dis[cur] < d: #???????????????\n",
    "#             #     continue\n",
    "            \n",
    "#             for nxt in edges[cur]:\n",
    "#                 if dis[nxt] > d + costs[nxt]:\n",
    "#                    dis[nxt] = d + costs[nxt]\n",
    "#                    heapq.heappush(heap,[dis[nxt],nxt])\n",
    "        \n",
    "#         return dis[n - 1] \n",
    "\n",
    "## topo\n",
    "        for i in range(n):\n",
    "            if minv[i] != -1:\n",
    "                edges[minv[i]].append(i)\n",
    "            if maxv[i] != -1:\n",
    "                edges[maxv[i]].append(i)\n",
    "        costs[0] = 0\n",
    "        for i in range(1, len(costs)):\n",
    "            if edges[i]:\n",
    "                costs[i] += min([costs[j] for j in edges[i]])\n",
    "        \n",
    "        return costs[-1]\n",
    "\n",
    "\n",
    "# 由于在某个位置上要么跳到第一个大于等于它的位置,要么跳到第一个小于它的位置;我们可以用单调栈求出每个位置可以跳到的下个位置,之后建边跑一边dijkstra即可。 时间复杂度:O(n*logn) 由于这个题的边存在索引大小限制,因此一定无环,也可以拓扑序dp,时间复杂度O(n)\n",
    "\n",
    "# 作者：Chap\n",
    "# 链接：https://leetcode.cn/problems/jump-game-viii/solutions/1592336/by-chap_-m8qx/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minv = [-1 for _ in range(n)]\n",
    "        maxv = [-1 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: minv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] < nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: maxv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            if minv[i] != -1:\n",
    "                edges[i].append(minv[i])\n",
    "            if maxv[i] != -1:\n",
    "                edges[i].append(maxv[i])\n",
    "\n",
    "        dis = [float('inf') for _ in range(n)]\n",
    "        dis[0] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0,0])\n",
    "        while heap:\n",
    "            d,cur = heapq.heappop(heap)\n",
    "            # if dis[cur] < d: #???????????????\n",
    "            #     continue\n",
    "            \n",
    "            for nxt in edges[cur]:\n",
    "                if dis[nxt] > d + costs[nxt]:\n",
    "                   dis[nxt] = d + costs[nxt]\n",
    "                   heapq.heappush(heap,[dis[nxt],nxt])\n",
    "        \n",
    "        return dis[n - 1] \n",
    "\n",
    "# 由于在某个位置上要么跳到第一个大于等于它的位置,要么跳到第一个小于它的位置;我们可以用单调栈求出每个位置可以跳到的下个位置,之后建边跑一边dijkstra即可。 时间复杂度:O(n*logn) 由于这个题的边存在索引大小限制,因此一定无环,也可以拓扑序dp,时间复杂度O(n)\n",
    "\n",
    "# 作者：Chap\n",
    "# 链接：https://leetcode.cn/problems/jump-game-viii/solutions/1592336/by-chap_-m8qx/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minv = [-1 for _ in range(n)]\n",
    "        maxv = [-1 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: minv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] < nums[i]: \n",
    "                stack.pop()\n",
    "            if stack: maxv[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            if minv[i] != -1:\n",
    "                edges[i].append(minv[i])\n",
    "            if maxv[i] != -1:\n",
    "                edges[i].append(maxv[i])\n",
    "\n",
    "        dis = [float('inf') for _ in range(n)]\n",
    "        dis[0] = 0\n",
    "        heap = []\n",
    "        heapq.heappush(heap,[0,0])\n",
    "        while heap:\n",
    "            d,cur = heapq.heappop(heap)\n",
    "            if dis[cur] < d:\n",
    "                continue\n",
    "            \n",
    "            for nxt in edges[cur]:\n",
    "                if dis[nxt] > d + costs[nxt]:\n",
    "                   dis[nxt] = d + costs[nxt]\n",
    "                   heapq.heappush(heap,[dis[nxt],nxt])\n",
    "        \n",
    "        return dis[n - 1] \n",
    "\n",
    "# 作者：Chap\n",
    "# 链接：https://leetcode.cn/problems/jump-game-viii/solutions/1592336/by-chap_-m8qx/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 单调栈+动态规划\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 找寻下一个 >= 当前值的索引\n",
    "        big = [0] * n\n",
    "        stack = [0]\n",
    "        for i in range(1, n):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                big[stack.pop()] = i\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        for ind in stack:\n",
    "            big[ind] = ind\n",
    "\n",
    "        # 找寻下一个 < 当前值的索引\n",
    "        small = [0] * n\n",
    "        stack = [0]\n",
    "        for i in range(1, n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                small[stack.pop()] = i\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        for ind in stack:\n",
    "            small[ind] = ind\n",
    "        \n",
    "        # 记录当前索引可能的上一跳\n",
    "        pre = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if big[i] > i:\n",
    "                pre[big[i]].append(i)\n",
    "\n",
    "            if small[i] > i:\n",
    "                pre[small[i]].append(i)\n",
    "        \n",
    "        # 动态规划计算最小代价\n",
    "        dp = [float('inf')]*n\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min([dp[j] for j in pre[i]]) + costs[i]\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        graph = collections.defaultdict(set)\n",
    "\n",
    "        for case in (-1, 1):\n",
    "            needs = list()\n",
    "            for i in range(len(nums)):\n",
    "                while needs and case * (nums[i] + 0.5) < case * nums[needs[-1]]:\n",
    "                    graph[i].add(needs.pop())\n",
    "                needs.append(i)\n",
    "\n",
    "        costs[0] = 0\n",
    "        for i in range(1, len(costs)):\n",
    "            costs[i] += min([costs[j] for j in graph[i]])\n",
    "        \n",
    "        return costs[-1]\n",
    "\n",
    "# 作者：Tianyu Zhang\n",
    "# 链接：https://leetcode.cn/problems/jump-game-viii/solutions/2303555/graph-search-by-tianyuzhang-v39i/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        graph = collections.defaultdict(set)\n",
    "\n",
    "        for case in (-1, 1):\n",
    "            needs = list()\n",
    "            for i in range(len(nums)):\n",
    "                while needs and case * (nums[i] + 0.5) < case * nums[needs[-1]]:\n",
    "                    graph[i].add(needs.pop())\n",
    "                needs.append(i)\n",
    "\n",
    "        costs[0] = 0\n",
    "        for i in range(1, len(costs)):\n",
    "            costs[i] += min([costs[j] for j in graph[i]])\n",
    "        \n",
    "        return costs[-1]\n",
    "\n",
    "# 作者：Tianyu Zhang\n",
    "# 链接：https://leetcode.cn/problems/jump-game-viii/solutions/2303555/graph-search-by-tianyuzhang-v39i/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxRange = getRange(nums, isMax=True, isRightStrict=True)\n",
    "        minRange = getRange(nums, isMax=False, isRightStrict=False)\n",
    "        adjMap = defaultdict(lambda: defaultdict(lambda: int(1e20)))\n",
    "        for cur, (next1, next2) in enumerate(zip(maxRange, minRange)):\n",
    "            next1, next2 = next1 + 1, next2 + 1\n",
    "            adjMap[cur][next1] = costs[next1] if next1 < n else int(1e20)\n",
    "            adjMap[cur][next2] = costs[next2] if next2 < n else int(1e20)\n",
    "        return dijkstra(adjMap, 0, n - 1)\n",
    "\n",
    "##############################################\n",
    "def getRange(nums: List[int], *, isMax=False, isRightStrict=False,) -> List[int]:\n",
    "    def compareRight(stackValue: int, curValue: int) -> bool:\n",
    "        if isRightStrict and isMax:\n",
    "            return stackValue <= curValue\n",
    "        elif isRightStrict and not isMax:\n",
    "            return stackValue >= curValue\n",
    "        elif not isRightStrict and isMax:\n",
    "            return stackValue < curValue\n",
    "        else:\n",
    "            return stackValue > curValue\n",
    "\n",
    "    n = len(nums)\n",
    "    rightMost = [n - 1] * n\n",
    "    stack = []\n",
    "    for i in range(n):\n",
    "        while stack and compareRight(nums[stack[-1]], nums[i]):\n",
    "            rightMost[stack.pop()] = i - 1\n",
    "        stack.append(i)\n",
    "    return rightMost\n",
    "\n",
    "##############################################\n",
    "from collections import defaultdict\n",
    "from heapq import heappop, heappush\n",
    "from typing import DefaultDict, Hashable, List, Optional, TypeVar, overload\n",
    "\n",
    "INF = int(1e20)\n",
    "Vertex = TypeVar('Vertex', bound=Hashable)\n",
    "Graph = DefaultDict[Vertex, DefaultDict[Vertex, int]]\n",
    "\n",
    "@overload\n",
    "def dijkstra(adjMap: Graph, start: Vertex) -> DefaultDict[Vertex, int]:\n",
    "    ...\n",
    "\n",
    "@overload\n",
    "def dijkstra(adjMap: Graph, start: Vertex, end: Vertex) -> int:\n",
    "    ...\n",
    "\n",
    "def dijkstra(adjMap: Graph, start: Vertex, end: Optional[Vertex] = None):\n",
    "    dist = defaultdict(lambda: INF)\n",
    "    dist[start] = 0\n",
    "    pq = [(0, start)]\n",
    "\n",
    "    while pq:\n",
    "        curDist, cur = heappop(pq)\n",
    "        if dist[cur] < curDist:\n",
    "            continue\n",
    "        if end is not None and cur == end:\n",
    "            return curDist\n",
    "        for next in adjMap[cur]:\n",
    "            if dist[next] > dist[cur] + adjMap[cur][next]:\n",
    "                dist[next] = dist[cur] + adjMap[cur][next]\n",
    "                heappush(pq, (dist[next], next))\n",
    "\n",
    "    return INF if end is not None else dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right_greater = [-1]*n\n",
    "        right_lesser = [-1]*n\n",
    "        sta_g = [(float('inf'),n)]\n",
    "        sta_l = [(-float('inf'),n)]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while sta_g[-1][0]<nums[i]:\n",
    "                sta_g.pop(-1)\n",
    "            right_greater[i] = sta_g[-1][1]\n",
    "            sta_g.append((nums[i],i))\n",
    "\n",
    "            while sta_l[-1][0]>=nums[i]:\n",
    "                sta_l.pop(-1)\n",
    "            right_lesser[i] = sta_l[-1][1]\n",
    "            sta_l.append((nums[i],i))\n",
    "        \n",
    "        rec = [-1]*n\n",
    "        def dfs(x):\n",
    "            #从x位置跳到n-1位置的最小代价\n",
    "            if x==n-1: return 0\n",
    "            if rec[x]!=-1:\n",
    "                return rec[x]\n",
    "            right_g = right_greater[x]\n",
    "            right_l = right_lesser[x]\n",
    "            res = float('inf')\n",
    "            if right_g<n:\n",
    "                res = min(res, costs[right_g] + dfs(right_g))\n",
    "            if right_l<n:\n",
    "                res = min(res, costs[right_l] + dfs(right_l))\n",
    "            rec[x] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        stk = []\n",
    "        g = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            l = i\n",
    "            while stk and stk[-1][-1] <= x: # 非递减单调栈\n",
    "                l, r, y = stk.pop() # y所影响的索引区间:[l, r](包括r)\n",
    "                # 额外的计算:\n",
    "                g[r].append(i)\n",
    "            stk.append((l, i, x))\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            l = i\n",
    "            while stk and stk[-1][-1] > x: #\n",
    "                l, r, y = stk.pop() # y所影响的索引区间:[l, r](包括r)\n",
    "                # 额外的计算\n",
    "                g[r].append(i)\n",
    "            stk.append((l, i, x))\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n-1: return 0\n",
    "            rnt = inf\n",
    "            for x in g[i]:\n",
    "                rnt = min(rnt, costs[x] + f(x))\n",
    "            return rnt             \n",
    "        return -1 if f(0) == inf else f(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        s = [0]\n",
    "        for i in range(1, n):\n",
    "            while s and nums[s[-1]] <= nums[i]:\n",
    "                g[s.pop()].append(i)\n",
    "            s.append(i)\n",
    "        s = [0]\n",
    "        for i in range(1, n):\n",
    "            while s and nums[s[-1]] > nums[i]:\n",
    "                g[s.pop()].append(i)\n",
    "            s.append(i)\n",
    "        \n",
    "        @cache \n",
    "        def f(i):\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "            candi = [i + 1]\n",
    "            candi.extend(g[i])\n",
    "            res = inf \n",
    "            for nxt in set(candi):\n",
    "                res = min(res, costs[nxt] + f(nxt))\n",
    "            return res \n",
    "        \n",
    "        ans = f(0)\n",
    "        f.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], costs: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        s = [0]\n",
    "        for i in range(1, n):\n",
    "            while s and nums[s[-1]] <= nums[i]:\n",
    "                g[s.pop()].append(i)\n",
    "            s.append(i)\n",
    "        s = [0]\n",
    "        for i in range(1, n):\n",
    "            while s and nums[s[-1]] > nums[i]:\n",
    "                g[s.pop()].append(i)\n",
    "            s.append(i)\n",
    "        \n",
    "        @cache \n",
    "        def f(i):\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "            candi = [i + 1]\n",
    "            candi.extend(g[i])\n",
    "            res = inf \n",
    "            for nxt in set(candi):\n",
    "                res = min(res, costs[nxt] + f(nxt))\n",
    "            return res \n",
    "        \n",
    "        return f(0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
